package com.study.algorithm;

import java.util.Arrays;

/**
 * 异或运^的妙用-->无进位相加 a^a=0;a^0=a;满足交换律和结合律
 */
public class Algorithm_1 {

  public static void main(String[] args) {
//    test01();
//    test02();
//    test03();
//    test04();
//    test05();
//    test06();
//    test07();
    test08();
  }

  private static boolean test08() {
    int[] arr = new int[]{10, 20, 30, 50, 60, 90, 100, 200, 300,400};
    int num = 60;
    int L = 0;
    int R = arr.length - 1;
    boolean flag = false;
    while (L < R) {
      int middle = L + ((R - L) >> 1);
      if (num > arr[middle]) {
        L = middle + 1;
      } else if (num == arr[middle]) {
        System.out.println(middle);
        flag = true;
        break;
      } else {
        R = middle - 1;
      }
    }
    System.out.println(flag);
    return flag;
  }

  private static void test07() {
    int[] arr = new int[]{6, 5, 40, 2, 3, 1, 7};
    pro(arr, 0, arr.length - 1);
    System.out.println(Arrays.toString(arr));
  }

  private static void pro(int[] arr, int L, int R) {
    if (L == R) {
      return;
    }
    int middle = L + ((R - L) >> 1);
    pro(arr, L, middle);
    pro(arr, middle + 1, R);
    merge(arr, L, middle, R);
  }

  private static void merge(int[] arr, int L, int M, int R) {
    int[] help = new int[R - L + 1];
    int i = 0;
    int p1 = L;
    int p2 = M + 1;
    while (p1 <= M && p2 <= R) {
      help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
    }
    while (p1 <= M) {
      help[i++] = arr[p1++];
    }
    while (p2 <= R) {
      help[i++] = arr[p2++];
    }
    for (int j = 0; j < help.length; j++) {
      arr[L + j] = help[j];
    }
  }

  private static void test06() {
    int[] arr = new int[]{6, 5, 40, 2, 3, 1, 7};
    int max = process(arr, 0, arr.length - 1);
    System.out.println(max);
  }

  private static int process(int[] arr, int L, int R) {
    if (L == R) {
      return arr[L];
    }
    int middle = L + ((R - L) >> 1);
    int leftMax = process(arr, L, middle);
    int rightMax = process(arr, middle + 1, R);
    return Math.max(leftMax, rightMax);
  }

  private static void test05() {
    int[] arr = new int[]{6, 5, 40, 2, 3, 1, 7};
    for (int i = 1; i < arr.length; i++) {
      for (int j = i; j > 0; j--) {
        if (arr[j - 1] > arr[j]) {
          swap(arr, j - 1, j);
        }
      }
    }
    System.out.println(Arrays.toString(arr));
  }

  private static void test04() {
    int[] arr = new int[]{6, 5, 40, 2, 3, 1, 7};
    for (int i = 0; i < arr.length; ++i) {
      for (int j = i; j < arr.length - 1; ++j) {
        if (arr[i] > arr[j + 1]) {
          swap(arr, i, j + 1);
        }
      }
    }
    System.out.println(Arrays.toString(arr));
  }

  private static void test03() {
    int[] arr = new int[]{6, 5, 40, 2, 3, 1, 7};
    for (int i = 0; i < arr.length - 1; ++i) {
      for (int j = 0; j < arr.length - i - 1; ++j) {
        if (arr[j] > arr[j + 1]) {
          swap(arr, j, j + 1);
        }
      }
    }
    System.out.println(Arrays.toString(arr));
  }

  private static void swap(int[] arr, int j, int k) {
    arr[j] = arr[j] ^ arr[k];
    arr[k] = arr[j] ^ arr[k];
    arr[j] = arr[j] ^ arr[k];
  }

  //给定一个数组 有两个数字(不相等)出现的次数为奇数次,其余数字出现的次数为偶数次,求出现奇数次的两个数字
  private static void test02() {
    int[] arr = new int[]{2, 3, 5, 6, 2, 3, 4, 4, 4, 4, 2, 2};
    int eof = 0;
    for (int i : arr) {
      eof ^= i;
    }
    //此时eof为两个出现奇数次数字的乘积 eof=a*b 因为a!=b所以eof一定不为0-->eof的二进制至少有一位为1(这里假定第8位)
    // -->假定a的第8位为1,b的第8位为0 按照第8为1可以把这批数分为两组(第8位为1和第8位为0)
    // 提取出最右边的1
    int rightOne = eof & (~eof + 1);
    int onlyOne = 0;
    for (int i : arr) {
      //只取第8位为1的或者第8位为0的数字(也就是只取一半) 这里取第8位为1的
      if ((rightOne & i) == 0) {
        onlyOne ^= i;
      }
    }
    //得到eof2为 a或者b
    System.out.println(onlyOne);
    System.out.println(eof ^ onlyOne);
  }

  //给定一个数组 数组中有一个数的个数为奇数,其他若干数的个数为偶数 求个数为奇数的这个数
  private static void test01() {
    int[] arr = new int[]{2, 5, 3, 3, 5, 2, 2};
    int eof = 0;
    for (int i : arr) {
      eof ^= i;
    }
    System.out.println(eof);
  }
}
